require 'yaml'

##
 # @version 1
def deep_copy obj
	YAML::load(YAML::dump(obj))
end

##
 # @version 1
module MinMax
	def chercher depth, maxDepth
		minMaxAlt = (depth % 2 == 1)
		
		if (depth == maxDepth) then
			points = calcPoints(minMaxAlt, grille)
			chemin = Array.new
		else
			eachCoup(minMaxAlt) do |coup|
				context = copy
				context.jouerCoup minMaxAlt, coup
				tmp_points, tmp_chemin = context.chercherRec(depth + 1, maxDepth)
				
				if (minMaxAlt and tmp_points > points) or (not minMaxAlt and tmp_points < points) then
					points = tmp_points
					chemin = tmp_chemin
					chemin << coup
				end
			end
		end
		
		return points, chemin
	end
end

##
 # @version 2
class BinaryTreeNodeValue
	include Comparable
	attr_reader :ngrille, :points, :depth
	attr_writer :ngrille, :points, :depth
	
	def <=> other
		if @ngrille == other.ngrille then
			if @depth == other.depth then
				if @points == other.points then
					return 0
				elsif @points > other.points then
					return 1
				end
			elsif @depth > other.depth then
				return 1
			end
		elsif @ngrille > other.ngrille then
			return 1
		end
		
		return -1
	end
end

##
 # @version 1
module AlphaBeta
	def chercher depth, maxDepth
		$max_visited = BinaryTree.new
		$min_visited = BinaryTree.new
		$min_visited_nb = 0
		$max_visited_nb = 0
		coup = chercherRec depth, maxDepth, -@@infinite, @@infinite
		puts "min visited: " + $min_visited_nb.to_s
		puts "max visited: " + $max_visited_nb.to_s
		coup
	end
	
	def chercherRec depth, maxDepth, alpha, beta
		$nb_noeuds += 1 if $nb_noeuds
		minMaxAlt = (depth % 2 == 1)
		
		if (depth == maxDepth) then
			points = calcPoints(minMaxAlt)
			chemin = Array.new
		else
			if (minMaxAlt) then
				points = -@@infinite
			else
				points = @@infinite
			end
			
			eachCoup(minMaxAlt) do |coup|
				context = copy
				context.jouerCoup minMaxAlt, coup
				
				b = 1
				#~ context.eachCase do |rcase, x|
					#~ unless (rcase.is_a? CaseTrou) then
						#~ if (rcase.is_a?((minMaxAlt ? joueur : adversaire).class)) then
							#~ b += 1
						#~ end
						#~ b = b * 2
					#~ end
				#~ end
				context.eachCase do |rcase, x|
					unless (rcase.is_a? CaseTrou) then
						if (rcase.is_a?((minMaxAlt ? joueur : adversaire).class)) then
							b += 1
						elsif (rcase.is_a?((minMaxAlt ? adversaire : joueur).class)) then
							b += 2
						end
						b = b * 4
					end
				end
				do_rec = true
				
				#~ nodeVal = BinaryTreeNodeValue.new
				#~ nodeVal.ngrille = b
				#~ nodeVal.depth = depth + 1
				#~ nodeVal.points = context.calcPoints(minMaxAlt)
				
				if minMaxAlt then
					do_rec = false unless $max_visited.add(b)
					$max_visited_nb += 1 if do_rec
				else
					do_rec = false unless $min_visited.add(b)
					$min_visited_nb += 1 if do_rec
				end
				
				if do_rec then
					#~ if minMaxAlt then
						#~ puts 'max:' + b.to_s
					#~ else
						#~ puts 'min:' + b.to_s
					#~ end
					
					tmp_points, tmp_chemin = context.chercherRec(depth + 1, maxDepth, alpha, beta)
					
					if (minMaxAlt and tmp_points > points) or (not minMaxAlt and tmp_points < points) then
						points = tmp_points
						chemin = tmp_chemin
						chemin << coup
						
						if minMaxAlt then
							alpha = [alpha, points].max
							break if points >= beta
						else
							beta = [alpha, points].min
							break if alpha >= points
						end
					end
				end
			end
		end
		
		chemin = Array.new unless chemin
		return points, chemin
	end
end

##
 # @version 1
class BacteriaAI < BacteriaGrille
	attr_writer :joueur, :adversaire
	attr_reader :joueur, :adversaire
	
	include AlphaBeta
	
	def initialize width, height
		super width, height
		@depth = 5
	end
	
	def self.from_grille grille
		ngrille = BacteriaAI.new(grille.width, grille.height)
		ngrille.grille = deep_copy(grille.grille)
		
		return ngrille
	end
	
	def eachCoup minMaxAlt
		i = 0
		eachCase do |rcase, orig|
			if (rcase.is_a? CaseVide) then
				eachAround orig  do |rcase2, dest|
					if (rcase2.is_a? @joueur.class) then
						i += 1
						yield Coup.new dest, orig
						break
					end
				end
			end
			
			if (rcase.is_a? @joueur.class) then
				eachJump orig do |rcase2, dest|
					if (rcase2.is_a? CaseVide) then
						i += 1
						yield Coup.new orig, dest
					end
				end
			end
		end
		
		return i
	end
	
	def calcPoints minMaxAlt
		points = 0
		eachCase do |rcase, orig|
			if (rcase.is_a? @joueur.class) then
				points += 1
			end
		end
		
		return points
	end
	
	def jouerCoup minMaxAlt, coup
		begin
			super coup, (minMaxAlt ? @joueur:@adversaire)
		rescue Exception => e
			#~ STDERR.puts e
		end
	end
	
	def meilleurCoup
		tmp_points, tmp_chemin = chercher(1, @depth)
		return nil if tmp_chemin == []
		return tmp_chemin.last
	end
	
	def copy
		return deep_copy(self)
	end
end

